package algorithm.sort;

/**
 * @author xutao
 * created 2020/3/16 17:58
 */
public class MergeSort implements Sort {
    @Override
    public String name() {
        return "归并排序";
    }

    @Override
    public void sort(Integer[] arr) {
        sort(arr, 0, arr.length - 1);
    }


    private void sort(Integer[] arr, int start, int end) {
        //已经分裂成一个元素了
        if (end <= start) {
            return;
        }
        //获取中间元素middle
        int middle = (end + start) / 2;

        sort(arr, start, middle);
        sort(arr, middle + 1, end);
        //归并
        if (arr[middle]>arr[middle+1]){
            merge(arr, start, middle, end);
        }
    }


    private void merge(Integer[] arr, int start, int middle, int end) {
        //需要进行归并处理的长度
        int length = end - start + 1;

        Integer[] repliArray = new Integer[length];

        System.arraycopy(arr, start, repliArray, 0, length);

        //处理左边的元素
        int l = start;
        //处理右边的元素
        int r = middle + 1;
        //归并的数组区间为[start,end]
        for (int i = start; i <= end; i++) {
            if (l>middle){
                //如果左边的元素已经处理完毕
                arr[i] = repliArray[r-start];
                r++;
            }else if (r>end){
                //如果右边的元素已经处理完毕
                arr[i] = repliArray[l-start];
                l++;
            }else if (repliArray[r-start]<repliArray[l-start]){
                arr[i] = repliArray[r-start];
                r++;
            }else{
                arr[i] = repliArray[l-start];
                l++;
            }
        }
    }
}
